package org.pupil.list.partitionList;

import org.pupil.list.IList;
import org.pupil.list.ListNode;

/**
 * @Description: 划分链表, leetcode：https://leetcode.cn/problems/partition-list/description/
 * @Author: pupil
 * @Date: 2024/07/30 下午 3:16
 */
public class PartitionList {

    /**
     * 题目介绍：
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     *
     * 原链表：6->5->3->4->2->1->1->7->null
     *
     * 1. 当 x = 4 时：
     * < x 区域：3->2->1->1->null
     * >= x 区域：6->5->4->7->null
     * 最后结果：3->2->1->1->6->5->4->7->null
     *
     * 2. 当 x = 8 时：
     * < x 区域：6->5->3->4->2->1->1->7->null
     * >= x 区域：null 没有大于8的
     * 最后结果：返回原链接
     */
    public static ListNode partitionList(ListNode head, int x) {
        ListNode leftHead = null, leftTail = null; // < x 区域  小头和小尾
        ListNode rightHead = null, rightTail = null; // >= x 区域  大头和大尾
        ListNode next = null; // 记录原链表遍历的下一个节点

        while (head != null){
            next = head.next; // 记录原链表遍历的下一个节点
            head.next = null; // 断开链接
            // < x 区域，小尾是新链接关系的最后一个节点
            if (head.val < x){
                if (leftHead == null){
                    leftHead = head;  // 设置小头
                }else {
                    leftTail.next = head; // 链接下一个节点
                }
                leftTail = head; // 更新小尾
            }else { // >= x 区域，大尾是新链接关系的最后一个节点
                if (rightHead == null){
                    rightHead = head; // 设置大头
                }else {
                    rightTail.next = head; // 链接下一个节点
                }
                rightTail = head; // 更新大尾
            }
            head = next; // 获取遍历原链表下一个节点
        }
        // 如果整个链表大于等于 x，则直接返回大头
        if (leftHead == null){
            return rightHead;
        }

        // 小尾指向大头
        leftTail.next = rightHead;
        return leftHead;
    }

    public static void main(String[] args) {
        ListNode head1 = IList.get(new int[]{6, 5, 3, 4, 2, 1, 1, 7});
        System.out.print("当x=4时：");
        ListNode listNode1 = partitionList(head1, 4);
        IList.ergodic(listNode1);

        System.out.println();
        System.out.println("---------------------------------");

        ListNode head2 = IList.get(new int[]{6, 5, 3, 4, 2, 1, 1, 7});
        System.out.print("当x=8时：");
        ListNode listNode2 = partitionList(head2, 8);
        IList.ergodic(listNode2);
    }
}
